#include "Tree.h"
typedef struct QueueNode
{
	BTNode* data;
	struct QueueNode* next;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue* p)
{
	assert(p);
	p->head = NULL;
	p->tail = NULL;
	p->size = 0;
}
void QueueDestory(Queue* p)
{
	assert(p);
	QNode* scout = p->head;
	while (scout != NULL)
	{
		QNode* nextnode = scout->next;
		free(scout);
		scout = nextnode;
	}
	p->head = p->tail = NULL;
	p->size = 0;
}
void QueuePush(Queue* p, BTNode* x)
{
	assert(p);
	QNode* newnode = (QNode*)malloc(sizeof(Queue));

	newnode->data = x;
	newnode->next = NULL;
	if (p->tail == NULL)
	{
		p->tail = p->head = newnode;
	}
	else
	{
		p->tail->next = newnode;
		p->tail = p->tail->next;
	}
	p->size++;
}
void QueuePop(Queue* p)
{
	assert(p->head);
	assert(p);
	if (p->head->next == NULL)
	{
		free(p->head);
		p->head = p->tail = NULL;
		return;
	}
	Queue* nextnode = p->head->next;
	free(p->head);
	p->head = nextnode;
	p->size--;
}
BTNode* QueueFront(Queue* p)
{
	assert(p);
	assert(p->head);

	return p->head->data;
}
int QueueBack(Queue* p)
{
	assert(p);
	assert(p->tail);

	return p->tail->data;
}
int QueueSize(Queue* p)
{
	assert(p);
	assert(p->head);

	return p->size;
}
int QueueEmpty(Queue* p)
{
	return p->head == NULL && p->tail == NULL;
}
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PrevOrder(root->leftchild);
	PrevOrder(root->rightchild);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->leftchild);
	printf("%d ", root->data);
	InOrder(root->rightchild);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->leftchild);
	PostOrder(root->rightchild);
	printf("%d ", root->data);
}
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->leftchild) + TreeSize(root->rightchild) + 1;
}
int TreeLevelSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	//root != NULL
	if (k == 1)
		return 1;

	return TreeKLevelSize(root->leftchild, k - 1) + TreeKLevelSize(root->rightchild, k - 1);
}
int TreeleafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->leftchild == NULL && root->rightchild == NULL)
	{
		return 1;
	}
	return TreeleafSize(root->leftchild) + TreeleafSize(root->rightchild);
}
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftheight = TreeHeight(root->leftchild);
	int rightheight = TreeHeight(root->rightchild);
	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}
int TreelevelSize(BTNode* root,int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return TreelevelSize(root->leftchild,k-1)+ TreelevelSize(root->rightchild,k-1);
}
bool isBalancedTrue(BTNode* root)
{
	if (root == NULL)
	{
		return true;
	}

	Queue q1;
	QueueInit(&q1);
	QueuePush(&q1, root);
	while (!QueueEmpty(&q1))
	{
		BTNode* temp = QueueFront(&q1);
		QueuePop(&q1);
		if (temp == NULL)
		{
			break;
		}
		QueuePush(&q1, temp->leftchild);
		QueuePush(&q1, temp->rightchild);

	}

	while (!QueueEmpty(&q1))
	{
		BTNode* temp = QueueFront(&q1);
		if (temp != NULL)
		{
			return false;
		}

		QueuePop(&q1);
	}
	QueueDestory(&q1);
	return true;
}
bool isSameTree(BTNode* p, BTNode* q)
{
	if (p == NULL && q != NULL || p != NULL && q == NULL)
	{
		return false;
	}
	if (p == NULL && q == NULL)
	{
		return true;
	}
	if (p->data != q->data)
	{
		return false;
	}
	return isSameTree(p->leftchild, q->leftchild) && isSameTree(p->rightchild, q->rightchild);
}
bool isSubtree(BTNode* root, struct BTNode* subRoot)
{
	if (root == NULL)
	{
		return false;
	}
	bool temp = isSameTree(root, subRoot);
	if (false)
	{
		return true;
	}

	return isSubtree(root->leftchild, subRoot) || isSubtree(root->rightchild, subRoot);
}
BTNode* find(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}
	BTNode* nnledt = find(root->leftchild, x);
	if (nnledt)
	{
		return nnledt;
	}

	BTNode* nnright = find(root->rightchild, x);
	if (nnright)
	{
		return nnright;
	}

	return NULL;
}
void LeveLOrder(BTNode* n1)
{
	Queue q1;
	QueueInit(&q1);
	QueuePush(&q1, n1);
	while (!QueueEmpty(&q1))
	{
		BTNode* temp = QueueFront(&q1);
		printf("%d ", temp->data);
		QueuePop(&q1);

		if (temp->leftchild)
		{
			QueuePush(&q1, temp->leftchild);
		}

		if (temp->rightchild)
		{
			QueuePush(&q1, temp->rightchild);
		}
	}
}
void Test01()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	PrevOrder(&n1);
}
void Test02()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	printf("%d ", TreeSize(&n1));
}
void Test03()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	printf("%d ", TreeleafSize(&n1));
}
void Test04()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	printf("%d ", TreeHeight(&n1));
}
void Test05()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	printf("%d ", TreelevelSize(&n1,4));
}

void Test06()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;

	BTNode n9, n10, n11, n12, n13, n14, n15, n16;
	n9.data = 1;
	n10.data = 2;
	n11.data = 3;
	n12.data = 4;
	n13.data = 5;
	n14.data = 10;
	n15.data = 7;
	n16.data = 8;
	n16.leftchild = NULL;
	n16.rightchild = NULL;
	n13.leftchild = NULL;
	n13.rightchild = NULL;
	n14.leftchild = NULL;
	n14.rightchild = NULL;
	n15.leftchild = NULL;
	n15.rightchild = NULL;
	n12.leftchild = NULL;
	n12.rightchild = NULL;
	n9.leftchild = &n10;
	n9.rightchild = &n11;
	n10.leftchild = &n12;
	n10.rightchild = &n13;
	n11.leftchild = &n14;
	n11.rightchild = &n15;
	n12.leftchild = &n16;
}
void Test07()
{
	BTNode n1, n2, n3, n4, n5, n6;
	n1.data = 3;
	n2.data = 4;
	n3.data = 5;
	n4.data = 1;
	n5.data = 2;
	n6.data = 0;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n5.leftchild = &n6;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;

	BTNode nn1, nn2, nn3;
	nn1.data = 4;
	nn2.data = 1;
	nn3.data = 2;
	nn1.leftchild = &nn2;
	nn1.rightchild = &nn3;
	nn2.leftchild = NULL;
	nn2.rightchild = NULL;
	nn3.leftchild = NULL;
	nn3.rightchild = NULL;
	printf("%d", isSubtree(&n1, &nn1));

}
void Test08()
{
	BTNode n1, n2, n3, n4, n5, n6;
	n1.data = 3;
	n2.data = 4;
	n3.data = 5;
	n4.data = 1;
	n5.data = 2;
	n6.data = 0;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n5.leftchild = &n6;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;

	BTNode nn1, nn2, nn3;
	nn1.data = 4;
	nn2.data = 1;
	nn3.data = 2;
	nn1.leftchild = &nn2;
	nn1.rightchild = &nn3;
	nn2.leftchild = NULL;
	nn2.rightchild = NULL;
	nn3.leftchild = NULL;
	nn3.rightchild = NULL;
}
void Test9()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8;
	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n2.leftchild = &n4;
	n2.rightchild = &n5;
	n3.leftchild = &n6;
	n3.rightchild = &n7;
	n4.leftchild = &n8;
	LeveLOrder(&n1);
}
void Test10()
{
	BTNode n1, n2, n3, n4, n5, n6, n7, n8,n9;
	n1.data = 3;
	n2.data = 9;
	n3.data = 20;
	n4.data = 15;
	n5.data = 7;
	n6.data = 6;
	n7.data = 7;
	n8.data = 8;
	n9.data = 9;
	n2.leftchild = NULL;
	n2.rightchild = NULL;
	n9.leftchild = NULL;
	n9.rightchild = NULL;
	n8.leftchild = NULL;
	n8.rightchild = NULL;
	n5.leftchild = NULL;
	n5.rightchild = NULL;
	n6.leftchild = NULL;
	n6.rightchild = NULL;
	n7.leftchild = NULL;
	n7.rightchild = NULL;
	n4.leftchild = NULL;
	n4.rightchild = NULL;
	n1.leftchild = &n2;
	n1.rightchild = &n3;
	n3.leftchild = &n4;
	n3.rightchild = &n5;
	printf("%d ",isBalancedTrue(&n1));
}
int main()
{
	Test9();
	return 0;
}
